package sort.advanced_sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Demo4_QuickSort_UnRecursion {
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    /**
     * 非递归实现快速排序
     * <p>
     * 使用栈来代替递归。
     * <p>
     * 递归实现就是通过partition来进行元素交换，并获得分治后区间，那么只需要用栈来记录分治的区间开始和结束
     */
    public static void quickSort(int[] arr, int lo, int hi) {
        //利用一个Map集合类型的栈来代替递归
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();

        Map<String, Integer> record = new HashMap<>();
        // 记录开始位置 key : "startIndex"  --> value : lo(开始下标)
        // 记录结束位置 key : "endIndex"  --> value : hi(开始下标)
        record.put("startIndex", lo);
        record.put("endIndex", hi);
        quickSortStack.push(record);
        // 循环结束条件，栈为空时
        while(!quickSortStack.isEmpty()){
            //出栈，获得开始和结束下标，进行partition
            Map<String, Integer> param = quickSortStack.pop();
            int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
            //每一轮基准元素的左边区间的开始和结束
            if(param.get("startIndex") < pivotIndex - 1){
                Map<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", pivotIndex - 1);
                quickSortStack.push(leftParam);
            }
            //每一轮基准元素的右边区间的开始和结束
            if(pivotIndex + 1 < param.get("endIndex")){
                Map<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex",pivotIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }
    public static int partition(int[] arr, int lo, int hi){
        int pivot = arr[lo];
        int mark = lo;
        for (int i = lo + 1; i <= hi; i++){
            if(arr[i] < pivot){
                mark++;
                swap(arr, i, mark);
            }
        }
        arr[lo] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
